A typical example of the digital signal processor is illustrated in FIG. 1 of the drawings. The digital signal processor shown in FIG. 1 largely comprises a binary multiplier 1 and a register 2, and the binary multiplier is provided with a partial-product producing and adding stage 3 and a final partial-product adding stage 4. A time series multi-bit input signal a.sub.i is supplied from input signal lines 5 to one of the input ports of the partial-product producing and adding stage 3. In the following description, the suffix i is assumed to be incremented by time. To the other input port of the partial-product producing and adding stage 3 is fed back a product from the register 2 through feedback lines 6 which is the product of the time series multi-bit input signals a.sub.1 to a.sub.i-1.
The digital signal processor thus arranged is capable of executing the calculation represented by Equation 1. EQU Pn=((. . . (a.sub.0 .times.a.sub.1).times.a.sub.2).times.. . .).times.a.sub.n-1) .times.a.sub.n (Eq. 1)
where Pn is the product from the multi-bit input signal a.sub.0 to the multi-bit input signal a.sub.n.
In order to achieve a high speed calculation, it is preferable to reduce the number of the partial products, because the partial-product producing and adding stage 3 consumes a substantial amount of time. For reduction in the number of partial products, the calculation may be executed in accordance with Booth's Algorithm described by Rubinfield, L. P. in "A Proof of the Modified Booth's Algorithm for Multiplication", IEEE Transactions on Computers, vol. C-24, No. 10, October 1975, pages 1014 to 1015. It is also preferable to employ a parallel adding operation in accordance with the Wallace tree described in High-Speed Calculation Techniques for Computer, pages 168 to 173, published by Modern Science Corporation, or in Microelectronics Journal vol. 14, No. 6, 1983, pages 49 to 57, published by Benn Electronics Publication Ltd, Luton.
The final partial-product adding stage 4 is also causative of the substantial amount of time consumption due to propagation of a carry signal from digit to digit in the direction toward the high order side. One of the solutions is the employment of carry look ahead techniques, and the carry look ahead techniques are described in, for example, High-Speed Calculation Techniques for Computer, pages 85 to 92, published by Modern Science Corporation. Even if the carry look ahead techniques are employed in a processor, it is impossible to decrease the propagation time period to zero. In general, the total time period D4 consumed in the calculation of Equation 1 is represented by Equation 2: EQU D4=n.times.(T1=T2) (Eq. 2)
where T1 is a processing time period consumed by the partial-product producing and adding stage 3 and T2 is a processing time period consumed by the final partial-product adding stage 4. The processing time period T1 is capable of reduction by using the Wallace tree or the Booth's algorithm, and the processing time period T2 is able to be decreased by using the carry look ahead techniques as described hereinbefore.
Another approach is proposed as the application of SD numbers ( Signed Digit numbers ) in IEEE Journal of Solid-State Circuits, vol. SC-22, No. 1, February 1987, pages 28 to 34. In an ordinary m-ary system, each number is represented by using m positive integers such as (0, 1, . . . , m-1), however, the identical number is represented in the SD number system by using (2m-1) integers including negative integers, zero and positive integers such as (-(m-1), . . . , -1, 0, 1, . . . , m-1). For example, any binary number is represented in the SD number system by using three digits (-1, 0, 1), and the three digits are indicated in a digital signal processor as (1 1).sub.2, (0 0).sub.2 and (0 1).sub.2, respectively. However, the three digits are represented in the following description as (-1).sub.SD, (0).sub.SD and (1).sub.SD, respectively, for the sake of simplicity. Moreover, any number is placed in round brackets with suffix 2, SD or 10 depending upon the system.
In an ordinary binary arithmetic operation, a carry signal produced in a certain digit is sometimes propagated over a plurality of digits, and, for this reason, the calculation speed is lowered. However, if the arithmetic operation is executed in the SD system, every carry signal is merely transferred to the subsequent digit, then the arithmetic operation is increased in speed. The arithmetic operation in the SD number system consists of the following two stages. First, an intermediate carry and an intermediate sum are produced in every digit, and, then, the intermediate carry of the n-1 digit is added to the intermediate sum of the n digit for producing the final sum. When the intermediate carry is produced in the n-1 digit and, accordingly, propagated to the subsequent digit, the intermediate sum is produced in the n digit in such a manner that the intermediate carry is canceled therewith. In the SD number system with radix of "2", the intermediate carry is either (1).sub.SD or (-1).sub.SD. When the n digit is by way of example supplied with the combination of the SD numbers (0).sub.SD and (1).sub.SD or the combination of the SD numbers (0).sub.SD and (-1), the intermediate sum is decided in such a manner that no carry is produced therein in consideration of the carry produced in the n-1 digit. For example, when the intermediate carry of (1).sub.SD or (-1).sub.SD is produced in the n-1 digit, the n digit produces the intermediate sum of (-1).sub.SD or (1).sub.SD for restricting the production of the carry in the n digit. In the second stage where the intermediate carry of the n-1 digit is added to the intermediate sum of the n digit, the final sum of the n digit is produced to be (0).sub.SD as a result of the canceling principle. This means that no carry bit is propagated from the n digit to the n+1 digit. The intermediate sums and the intermediate carries are produced in all of the digits from n=1 to n=k in this manner, and, accordingly, the two k bit input signals are added without any carry propagation beyond the subsequent digit. Table 1 is indicative of the adding operations in the SD number system with the radix of "2" .
TABLE 1 ______________________________________ n digit of n digit of inter- inter- first input second input n-1 digit of mediate mediate signal signal both signals carry sum ______________________________________ 0 0 -- 0 0 0 1 Neither is 1 -1 negative At least one 0 1 is negative 0 -1 Neither is 0 -1 negative At least one -1 1 is negative 1 1 -- 1 0 1 -1 -- 0 0 -1 -1 -- -1 0 ______________________________________
For better understanding of the arithmetic operation in binary and SD number systems, an example is illustrated in FIGS. 2A and 2B. In FIG. 2A, two two's complements are added to each other, and an adding operation is carried out for two SD numbers corresponding to the two's complements in FIG. 2B. Assuming now that two decimal numbers A and B are represented as (7).sub.10 and (-15).sub.10, respectively, the decimal numbers A and B are converted into two two's complements (0 0 1 1 1).sub.2 and (1 0 0 0 1).sub.2, respectively and into two SD numbers (0 0 1 1 1).sub.SD and (-1 0 0 0 1), respectively. As shown in FIG. 2A, a carry C1 is produced at the lowest digit in the binary adding operation and propagated over three digits as indicated by arrows A1, A2 and A3. However, in the adding operation of the SD numbers, the two's complements A and B are firstly converted into the SD numbers A and B and, then, added to each other. The size of any k bit two's complements CMPk (x.sub.k, . . . , x.sub.2, x.sub.1) is calculated as ##EQU1## where the operator (*) stands for the multiplication and x.sub.k is the sign bit. When the sign bit is "1" or the two's complement is a negative integer, the two's complement is converted into an SD number (-1, x.sub.k-1, . . . , x.sub.2, x.sub.1).sub.SD. However, if zero is given to the sign bit x.sub.k or the two's complement is a positive integer, the two's complement is converted into an SD number (0, x.sub.k-1, converted into the two's complements which in turn are converted into the two SD numbers. In the adding operation of the two SD numbers, the intermediate sums and the intermediate carries are firstly produced in accordance with Table 1. Since each cf the lowest digits is (1).sub.SD, the intermediate sum of (0).sub.SD and the intermediate carry of (1).sub.SD are produced therefrom. The second digits are (1).sub.SD and (0).sub.SD, respectively, then the second digits produces the intermediate sum of (-1).sub.SD and the intermediate carry of (1).sub.SD in accordance with Table 1. Thus, the similar operations are carried out for the third digits to the highest digits, and, accordingly, the intermediate sums of (-1 0 -1 -1 0).sub.SD and the intermediate carries of (0 0 1 1 1).sub.SD are produced. Finally, the intermediate sums are added to the intermediate carries to yield the final sum of (-1 1 0 0 0).sub.SD. The SD number (-1 1 0 0 0).sub.SD is equivalent to the decimal number of (-8).sub.10, then the calculation result is verified to be correct. As shown in Table 1, the carry propagation over two digits is prohibited from the adding operations by avoiding any combination of the intermediate sum and the intermediate carry, i.e., the combination of the intermediate sum of (1).sub.SD and the intermediate carry of (1).sub.SD and the combination of the intermediate sum of (-1).sub.SD and the intermediate carry of (- 1).sub.SD, and, for this reason, the carry is merely transferred to the subsequent digit as shown in FIG. 2B. This carry propagation is expected to be conducive to improvement in processing speed of the signal processor.
FIG. 3 shows the arrangement of another prior-art signal processor using the principles of the adding operation on the SD numbers. The signal processor shown in FIG. 3 largely comprises a binary multiplier 11 and a register 12, and the binary multiplier 11 performs an arithmetic operation on two SD numbers. For this purpose, the binary multiplier 11 is provided with two binary number-to-SD number converting units 13 and 14 one of which is supplied with a time series multi-bit input signal and the other of which is operative to convert a binary number fed back from the register 12. Both of the binary number-to-SD number converting units 13 and 14 are coupled in parallel to a multiplier 15 executing a multiplication for SD numbers ( which is hereinunder referred to an SD multiplier ), then two SD numbers are multiplied in accordance with Table 1. The product is of the SD number, then the SD multiplier is followed by an SD number-to-binary number converting unit 16. The SD multiplier 15 is relatively large in processing speed with respect to the partial-product producing and adding stage 3 forming part of the digital signal processor shown in FIG. 1 as reported in IEEE Journal of Solid-State Circuits, vol. SC-22, No. 1, February 1987, pages 28 to 34. The SD number-to-binary number converting unit 16 is similar to the final partial-product adding stage 4 as described in High-Speed Calculation Techniques for Computer, page 13, published by Modern Science Corporation, and, for this reason, the SD number-to-binary number converting unit 16 consumes a time period approximately equal to the processing time T2. The binary number-to-SD number converting units 13 and 14 consume a negligible amount of time. Assuming now that the SD multiplier 15 consumes a processing time T3 less than the processing time T1, the digital signal processor shown in FIG. 3, the total time period D5 calculated by Equation 4 is consumed by the digital signal processor with the SD multiplier 15 for the progression represented by Equation 1: EQU D5=n.times.(T2+T3) (Eq. 4)
As described hereinbefore, the time period consumed by each binary number-to-SD number converting unit 13 or 14 is extremely short with respect to the processing times T2 and T3 ( see IEEE Journal of Solid-State Circuits, vol. SC-2, No. 1, February 1987, pages 28 to 34), and, for this reason, Equation 4 does not take into account of the time periods consumed by the converting units 13 and 14.
A problem is encountered in the prior-art digital signal processor shown in FIG. 1 is a low processing speed due to the carry propagation over a plurality of digits. When the digital - signal processor by way of example executes a calculation for a progression, the problem becomes serious, because the processor repeats the multiplication n times. The digital signal processor shown in FIG. 3 is slightly improved in processing speed by virtue of the SD multiplier 15, however, the SD number-to-binary number converting unit 16 consumes the time period approximately equal to that consumed by the final partial-product adding stage 4, so that the improvement in processing speed is limited.